package com.ting.test.algorithms.二叉树;


import java.util.List;

/**
 * 给定一棵二叉树的头节点head，和另外两个节点a和b。
 * 返回a和b的最低公共祖先
 * <p>
 * 利用递归的套路解答
 */
public class 最大快乐值 {
    public static void main(String[] args) {
        Employ head = new Employ();

        Info result = process(head);
        System.out.println(Math.max(result.no, result.yes));
    }

    private static Info process(Employ boss) {
        if (boss == null) {
            return new Info(0, 0);//如果当前节点值为空 则都为0
        }
        int yes = boss.happy;
        int no = 0;
        if (null!=boss.employList) {
            for (Employ next : boss.getEmployList()) {
                yes += process(next).no;
                no += process(next).yes;
            }
        }
        return new Info(no, yes);
    }

    static class Info {
        private int no;//表示当前节点来时能够获得的最大快乐值
        private int yes;//表示当前节点不来时能够获得的最大快乐值

        public Info(int no, int yes) {
            this.no = no;
            this.yes = yes;
        }
    }


    static class Employ {
        private int happy;//快乐值
        List<Employ> employList;

        public int getHappy() {
            return happy;
        }

        public List<Employ> getEmployList() {
            return employList;
        }
    }

}
